var findKthLargest = function (nums, k) {
  if (nums === null) return -1
  return quickSelect(nums, 0, nums.length - 1, k)
};

const quickSelect = (nums, start, end, k) => {
  if (start === end) return nums[start]

  let i = start
  let j = end
  let pivot = nums[(i + j) / 2]
  while (i <= j) {
    while (i <= j && nums[i] > pivot) {
      i++
    }
    while (i <= j && nums[j] < pivot) {
      j--
    }
    if (i <= j) {
      let temp = nums[i]
      nums[i] = nums[j]
      nums[j] = temp
      i++
      j--
    }
  }
  if (start + k - 1 <= j) {
    return quickSelect(nums, start, j, k)
  }
  if (start + k - 1 >= i) {
    return quickSelect(nums, i, end, k - (i - start))
  }
  return nums[j + 1]
}